﻿using System;
using System.Collections.Generic;

namespace Project1
{
	/// <summary>
	/// An implementation of the Breadth-First-Search algorithm.
	/// </summary>
    class BreadthFirstSearch : AbstractSearch
    {
		/// <summary>
		/// Performs a breadth first search
		/// </summary>
		/// <param name="problem">The search problem.</param>
		/// <returns>The goal state if a solution exists, otherwise <c>null</c>.</returns>
		protected override State PerformSearch(IProblem problem)
		{
			//
			// Use a FIFO queue for the frontier
			//
			Queue<State> frontier = new Queue<State>();
			//
			// Use a hashset for the explored (CLOSED) list
			//
			HashSet<Object> explored = new HashSet<object>();
			//
			// Is the initial state also the goal state?
			//
			State state = problem.InitialState;
			if (problem.IsGoal(state))
			{
				return state; // Problem? There is no problem!
			}
			//
			// Place the initial state on the frontier. Then loop until a solution or found or the 
			// entire search space has been explored.
			//
			frontier.Enqueue(state);
			while (true)
			{
				//
				// Have we emptied the frontier?
				//
				if (frontier.Count == 0)
				{
					//
					// No solution
					//
					return null;
				}
				//
				// Pop a state/node off the frontier and place it on the explored (CLOSED) list
				//
				state = frontier.Dequeue();
				explored.Add(state.Key);
				//
				// Performance metric bookkepping
				//
				base.StateExpanded();
				base.SetCurrentTreeSize(base.ExpandedStates + frontier.Count);
				//
				// Iterate through the successor states of the current state
				//
				foreach (State successor in problem.GetSuccessors(state))
				{
					//
					// If the successor has already been explored or placed on the frontier then we can discard it
					//
					if (explored.Contains(successor.Key) || frontier.Contains(successor))
					{
						continue;
					}
					//
					// Is this the goal state?
					//
					if (problem.IsGoal(successor))
					{
						base.SetCurrentTreeSize(base.ExpandedStates + frontier.Count + 1);
						return successor;
					}
					//
					// Place successor on frontier
					//
					frontier.Enqueue(successor);
				}
			}
		}
    }
}
